package com.company.algo.niuke;

import java.util.Stack;

import static java.lang.Character.isDigit;

/**华为：表达式求值
 请写一个整数计算器，支持加减乘三种运算和括号。
 es:
 输入"(2*(3-4))*5"，返回值-10
 输入"3+2*3*4-1"，返回值26
 */
public class ExpressionEvaluation {
    int calculate(String s){
        return helper(s);
    }
    int i = 0;
    int helper(String s){
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char sign = '+';
        while (i<s.length()){
            char c = s.charAt(i);
            if (isDigit(c)) num = 10*num + (c-'0');
            if (c == '(') { //遇到左括号开始递归计算 num
                i+=1;
                num = helper(s);
            }
            if (!isDigit(c) && c != ' ' || i == s.length()-1){
                int pre;
                switch (sign){                     //sign永远记录的是上一个运算符，如当前为a+b*c，则sign = '+' 而非 '*'
                    case '+':
                        stack.push(num);break;
                    case '-':
                        stack.push(-num);break;
                    //只要拿出前一个数字就做对应运算(乘除法优先级高)
                    case '*':
                        pre = stack.pop();
                        stack.push(pre*num);
                        break;
                    case '/':
                        pre = stack.pop();
                        stack.push(pre/num);
                        break;
                }
                //更新符号为当前符号，数字清零
                sign = c;
                num = 0;
            }
            if (c == ')') break;                        //遇到右括号返回递归结果
            i++;
        }
        //将栈中所有结果求和就是答案
        int res = 0;
        while (!stack.isEmpty()){
            res += stack.pop();
        }
        return res;
    }

    public static void main(String[] args) {
        ExpressionEvaluation Main = new ExpressionEvaluation();
        System.out.println(Main.calculate("3*(4-5/2)-6"));
    }

}
